package dataStructure.sort.shellSort;

import java.util.Arrays;

/**
 * @author lhn
 * @date 2024-08-30 14:25
 */

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        System.out.println("排序前：");
        System.out.println(Arrays.toString(arr));
//        ShellSort.sort(arr);
        ShellSort.sort_2(arr);
        System.out.println("排序后：");
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        int gap = arr.length / 2;
        int count = 0;
        while (gap > 0) {
            System.out.println("gap = " + gap);

            //从索引 gap 开始，一直到数组末尾
            for (int i = gap; i < arr.length; i++) {
                System.out.println("i = " + i);

                //在子序列中，从第gap个元素，逐个与子序列前面元素比较，交换位置
                for (int j = i; j >= gap; j = j - gap) {
                    System.out.print("|_____j = ");
                    System.out.println(j + " compare with " + (j - gap));
                    if (arr[j] < arr[j - gap]) {
                        int temp = arr[j - gap];
                        arr[j - gap] = arr[j];
                        arr[j] = temp;
                    }

                }
            }
            System.out.println("第" +(++count)+"轮结果：" + Arrays.toString(arr));
            gap = gap / 2;
        }

    }

    // 希尔排序的移动优化
    public static void sort_2(int[] arr) {
        int gap = arr.length / 2;
        int count = 0;
        while (gap > 0) {
            System.out.println("gap = " + gap);

            for (int i = gap; i < arr.length; i++) {
                int j = i;  //存放临时下标
                int temp = arr[j]; //存放临时变量
                if (arr[j] < arr[j - gap]) {
                    //  j >= gap确保索引不越界
                    while (j >= gap && arr[j - gap] > temp) {
                        arr[j] = arr[j - gap];
                        j = j - gap;
                    }
                    arr[j] = temp;
                }
            }
            System.out.println("第" +(++count)+"轮结果：" + Arrays.toString(arr));
            gap = gap / 2;
        }
    }
}
/**
 排序前：
 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
 gap = 5
 i = 5
 |_____j = 5 compare with 0
 i = 6
 |_____j = 6 compare with 1
 i = 7
 |_____j = 7 compare with 2
 i = 8
 |_____j = 8 compare with 3
 i = 9
 |_____j = 9 compare with 4
 第1轮结果：[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
 gap = 2
 i = 2
 |_____j = 2 compare with 0
 i = 3
 |_____j = 3 compare with 1
 i = 4
 |_____j = 4 compare with 2
 |_____j = 2 compare with 0
 i = 5
 |_____j = 5 compare with 3
 |_____j = 3 compare with 1
 i = 6
 |_____j = 6 compare with 4
 |_____j = 4 compare with 2
 |_____j = 2 compare with 0
 i = 7
 |_____j = 7 compare with 5
 |_____j = 5 compare with 3
 |_____j = 3 compare with 1
 i = 8
 |_____j = 8 compare with 6
 |_____j = 6 compare with 4
 |_____j = 4 compare with 2
 |_____j = 2 compare with 0
 i = 9
 |_____j = 9 compare with 7
 |_____j = 7 compare with 5
 |_____j = 5 compare with 3
 |_____j = 3 compare with 1
 第2轮结果：[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
 gap = 1
 i = 1
 |_____j = 1 compare with 0
 i = 2
 |_____j = 2 compare with 1
 |_____j = 1 compare with 0
 i = 3
 |_____j = 3 compare with 2
 |_____j = 2 compare with 1
 |_____j = 1 compare with 0
 i = 4
 |_____j = 4 compare with 3
 |_____j = 3 compare with 2
 |_____j = 2 compare with 1
 |_____j = 1 compare with 0
 i = 5
 |_____j = 5 compare with 4
 |_____j = 4 compare with 3
 |_____j = 3 compare with 2
 |_____j = 2 compare with 1
 |_____j = 1 compare with 0
 i = 6
 |_____j = 6 compare with 5
 |_____j = 5 compare with 4
 |_____j = 4 compare with 3
 |_____j = 3 compare with 2
 |_____j = 2 compare with 1
 |_____j = 1 compare with 0
 i = 7
 |_____j = 7 compare with 6
 |_____j = 6 compare with 5
 |_____j = 5 compare with 4
 |_____j = 4 compare with 3
 |_____j = 3 compare with 2
 |_____j = 2 compare with 1
 |_____j = 1 compare with 0
 i = 8
 |_____j = 8 compare with 7
 |_____j = 7 compare with 6
 |_____j = 6 compare with 5
 |_____j = 5 compare with 4
 |_____j = 4 compare with 3
 |_____j = 3 compare with 2
 |_____j = 2 compare with 1
 |_____j = 1 compare with 0
 i = 9
 |_____j = 9 compare with 8
 |_____j = 8 compare with 7
 |_____j = 7 compare with 6
 |_____j = 6 compare with 5
 |_____j = 5 compare with 4
 |_____j = 4 compare with 3
 |_____j = 3 compare with 2
 |_____j = 2 compare with 1
 |_____j = 1 compare with 0
 第3轮结果：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
 排序后：
 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/